package demo8;

/**
 * 01背包-分割等和子集
 */
public class test3 {
    public boolean canPartition(int[] nums) {
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        if(sum % 2 != 0) return false;
        // 创建dp表
        int aim = sum / 2;
        int n = nums.length;
        boolean[][] dp = new boolean[n+1][aim + 1];
        // 初始化
        for(int i =0;i<=n;i++){
            dp[i][0] = true;
        }
        for(int i =1;i<=n;i++){
            for(int j =1;j<=aim;j++){
                dp[i][j] = dp[i-1][j];
                if(j >= nums[i-1]){
                    dp[i][j] = dp[i][j] || dp[i-1][j - nums[i-1]];
                }
            }
        }
        return dp[n][aim];
    }

    // 优化
    public boolean canPartition2(int[] nums) {
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        if(sum % 2 != 0) return false;
        // 创建dp表
        int aim = sum / 2;
        int n = nums.length;
        boolean[] dp = new boolean[aim + 1];
        // 初始化
        dp[0] = true;

        for(int i =1;i<=n;i++){
            for(int j =aim;j>=nums[i-1];j--){ // 修改遍历顺序
                dp[j] = dp[j] || dp[j - nums[i-1]];
            }
        }
        return dp[aim];
    }
}
